package com.felix.algorithms.tree;

import lombok.Data;

/**
 * BinaryNode
 *
 * @author xuejinhua
 * @date 2018/9/10 11:11
 */
@Data
public class BinaryNode<T> implements BinaryNodeInterface<T>, java.io.Serializable {

    private T data;
    private BinaryNode left;
    private BinaryNode right;

    public BinaryNode() {
        this(null);
    }

    /**
     * 构造一个值为dataPortion的结点
     * @param dataPortion
     */
    public BinaryNode(T dataPortion) {
        this(dataPortion, null, null);
    }

    public BinaryNode(T dataPortion, BinaryNode leftChild, BinaryNode rightChild) {
        data = dataPortion;
        left = leftChild;
        right = rightChild;
    }

    @Override
    public BinaryNodeInterface<T> getLeftChild() {
        return left;
    }

    @Override
    public BinaryNodeInterface<T> getRightChild() {
        return right;
    }

    @Override
    public void setLeftChild(BinaryNodeInterface<T> leftChild) {
        this.left = (BinaryNode) leftChild;
    }

    @Override
    public void setRightChild(BinaryNodeInterface<T> rightChild) {
        this.right = (BinaryNode) rightChild;
    }

    @Override
    public boolean hasLeftChild() {
        return left != null;
    }

    @Override
    public boolean hasRightChild() {
        return right != null;
    }

    @Override
    public boolean isLeaf() {
        return (left == null) && (right == null);
    }

    @Override
    public int getNumberOfNodes() {
        int leftNumber = 0;
        int rightNumber = 0;
        if (left != null) {
            leftNumber = left.getNumberOfNodes();
        }
        if (right != null) {
            rightNumber = right.getNumberOfNodes();
        }
        return 1 + leftNumber + rightNumber;
    }

    /**
     * 返回以此结点为根的子树的高度
     *
     * @return
     */
    @Override
    public int getHeight() {
        return getHeight(this);
    }

    private int getHeight(BinaryNode<T> node) {
        int height = 0;
        if (node != null) {
            height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
        }
        return height;
    }

    @Override
    public BinaryNodeInterface<T> copy() {
        BinaryNode<T> newRoot = new BinaryNode<>(data);
        if (left != null) {
            newRoot.left = (BinaryNode<T>) left.copy();
        }
        if (right != null) {
            newRoot.right = (BinaryNode<T>) right.copy();
        }
        return newRoot;
    }
}
